/**
 * 版权所有 (C), 2019-2019, XXX有限公司
 * 项目名：com.company.study.dsa.recursive
 * 文件名: SplitSearchTest
 * 日期: 2019/6/18 15:18
 * 说明:
 */
package com.company.study.dsa.recursive;

/**
 * 二分查找
 *
 * @author Anbang713
 * @create 2019/6/18
 */
public class SplitSearchTest {

    /**
     * 不使用递归。<br>
     * 找到目标值返回数组下标，找不到返回-1
     *
     * @param array
     * @param key
     * @return
     */
    public static int findTwoPoint(int[] array, int key) {
        int start = 0;
        int last = array.length - 1;
        while (start <= last) {
            int mid = (last - start) / 2 + start;//防止直接相加造成int范围溢出
            if (key == array[mid]) {//查找值等于当前值，返回数组下标
                return mid;
            }
            if (key > array[mid]) {//查找值比当前值大
                start = mid + 1;
            }
            if (key < array[mid]) {//查找值比当前值小
                last = mid - 1;
            }
        }
        return -1;
    }

    /**
     * 使用递归
     *
     * @param array
     * @param key
     * @param low
     * @param high
     * @return
     */
    public static int search(int[] array, int key, int low, int high) {
        int mid = (high - low) / 2 + low;
        if (key == array[mid]) {//查找值等于当前值，返回数组下标
            return mid;
        } else if (low > high) {//找不到查找值，返回-1
            return -1;
        } else {
            if (key < array[mid]) {//查找值比当前值小
                return search(array, key, low, mid - 1);
            }
            if (key > array[mid]) {//查找值比当前值大
                return search(array, key, mid + 1, high);
            }
        }
        return -1;
    }
}